#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
class Solution1 {
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int len = 0, left = 0, right = 0, cnt = 0, n = nums.size();
        while (right < n)
        {
            if (right == 9)
            {
                int a = 0;
            }
            if (cnt < k && nums[right] == 0)
            {
                cnt++;
                len = max(len, right - left + 1);
            }
            else if (nums[right] == 1)
            {
                len = max(len, right - left + 1);
            }
            else
            {
                while (nums[left] != 0)
                {
                    left++;
                }
                left++;
            }
            right++;
        }
        return len;
    }
};
class Solution6 {
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int len = 0, left = 0, right = 0, cnt = 0, n = nums.size();
        while (right < n)
        {
            if (nums[right] == 0)cnt++;
            len = max(len, right - left + 1);
            while (cnt > k)
            {
                if (nums[left++] == 0)cnt--;
            }

            right++;
        }
        return len;
    }
};
class Solution123 {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int Sum = 0;
        for (auto e : nums)
        {
            Sum += e;
        }
        int target = Sum - x;
        if (target < 0)
            return -1;
        if (target == 0)
            return nums.size();
        int left = 0, right = 0, sum = 0, len = 0;
        while (left <= right && right < nums.size())
        {
            sum += nums[right];
            while (sum > target)
            {
                sum -= nums[left];
                left++;
            }
            if (sum == target)
            {
                len = max(len, right - left + 1);
                right++;
                sum += nums[right];
                sum -= nums[left];
                left++;
            }
            right++;
        }
        if (len)
            return nums.size() - len;
        else
            return -1;
    }
};
class Solution115 {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int Sum = 0;
        for (auto e : nums)
        {
            Sum += e;
        }
        int target = Sum - x;
        if (target < 0)
            return -1;
        /*if (target == 0)
            return nums.size();*/
        int left = 0, right = 0, sum = 0, len = 0;
        while (left <= right && right < nums.size())
        {
            sum += nums[right];
            while (sum > target)
            {
                sum -= nums[left];
                left++;
            }
            if (sum == target)
            {
                len = max(len, right - left + 1);
            }
            right++;
        }
        if (len)
            return nums.size() - len;
        else
            return -1;
    }
};
class Solution512
{
public:
    int totalFruit(vector<int>& fruits)
    {
        map<int, int> cnt;
        int left = 0, right = 0, len = 0;
        while (right < fruits.size())
        {
            cnt[fruits[right]]++;
            while (cnt.size() > 2)
            {
                cnt[fruits[left]]--;
                if (cnt[fruits[left]] == 0)
                {
                    cnt.erase(fruits[left]);
                }
                left++;
            }
            len = max(len, right - left + 1);
            right++;
        }
        return len;
    }
};
class Solution546
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> v;
        unordered_map<char, int> hash1, hash2;
        for (auto e : p)
        {
            hash1[e]++;
        }
        int left = 0, right = p.size() - 1;
        for (int i = 0;i < right;++i)
        {
            hash2[s[i]]++;
        }
        while (right < s.size())
        {
            if (hash2 == hash1)
            {
                v.push_back(left);
            }
            right++;
            hash2[s[right]]++;
            hash2[s[left]]--;
            if (hash2[s[left]] == 0)
            {
                hash2.erase(s[left]);
            }
            left++;
        }
        return v;
    }
};
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> v;
        int len = words[0].size();
        int hash1_amount = 0;
        unordered_map<string, int> hash1;
        for (auto e : words)
        {
            hash1[e]++;
            hash1_amount++;
        }

        for (int i = 0;i < len;i++)
        {
            if (i == 0)
            {
                int a = 0;
            }
            if (i == 1)
            {
                int a = 0;
            }
            if (i == 2)
            {
                int a = 0;
            }
            auto left = s.begin() + i, right = s.begin() + i;
            int cnt = 0;
            unordered_map<string, int> hash2;
            int hash2_amount = 0;
            while (right <= s.end() - len)
            {
                string tmp(right, right + len );
                hash2[tmp]++;
                hash2_amount++;
                if (hash1.find(tmp)!=hash1.end() && hash2[tmp] <= hash1[tmp]) cnt++;
                if (hash2_amount > hash1_amount)
                {
                    string tmp1 = string(left, left + len );
                    if (hash1.find(tmp1) != hash1.end() && hash2[tmp1] <= hash1[tmp1])
                    {
                        cnt--;
                    }
                    hash2[tmp1]--;
                    if (hash2[tmp1] == 0)
                        hash2.erase(tmp1);
                    left += len;
                }
                if (cnt == hash1_amount)
                {
                    v.push_back(left - s.begin());
                }
                right += len;
            }
        }
        return v;
    }
};
int main()
{
    string s = "";
    vector<string> v= {"foo", "bar"};
    Solution().findSubstring(s, v);
	return 0;
}